package com.zp.self.module.level_4_算法练习.算法.双指针.左右指针;
import org.junit.Test;

/**
 * @author By ZengPeng
 */
public class 力扣_1013_将数组分成和相等的三个部分 {
    @Test
    public void main() {
        
        Solution solution = new 力扣_1013_将数组分成和相等的三个部分().new Solution();
        System.out.println(solution);
    }

    /**
     题目：给你一个整数数组 arr，只有可以将其划分为三个和相等的 非空 部分时才返回 true，否则返回 false。
         形式上，如果可以找出索引 i + 1 < j 且满足 (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1]) 就可以将数组三等分。

         示例 1：
         输入：arr = [0,2,1,-6,6,-7,9,1,2,0,1]
         输出：true
         解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

         示例 2：
         输入：arr = [0,2,1,-6,6,7,9,-1,2,0,1]
         输出：false

         示例 3：
         输入：arr = [3,3,6,5,-2,2,5,1,-9,4]
         输出：true
         解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

     分析：【P 💖💖】
        1.遍历+左右指针：先求出总和/3 ;然后左右两边分别能否相加得到这个和
                --执行耗时:1 ms,击败了100.00% 的Java用户
                --编码耗时:[12:57]

     边界值 & 注意点：
        1.
     **/
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean canThreePartsEqualSum(int[] arr) {
        int sum=0;
        for (int i : arr)
            sum+=i;
        if(sum%3!=0)return false;
        int part = sum/3;
        int left = 0,right = arr.length-1,length=arr.length;
        while (left<length){
            part-=arr[left];
            if(part==0)break;
            left++;
        }
        part = sum/3;
        while (right>0){
            part-=arr[right];
            if(part==0)break;
            right--;
        }
        return right != 0 && left != length && right - left >1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}